#pragma once

#include "BinaryTreeBase.h"


template<typename T, typename NodeType=BTNode<T>>
class BST: public BinaryTreeBase<T, NodeType>
{
public:
	using Node = NodeType;
	
	BST();
	~BST();
	
	/**
	 * 搜索 key 对应的元素
	 * @param key 
	 * @return 如果 key 不存在，返回 nullptr
	 */
	Node* Search(const T& key) const;
	
	/**
	 * 查找最大值
	 * @return 
	 */
	Node* FindMax(Node* rootNode) const;
private:
	/**
	 * 递归搜索
	 * @param key 
	 * @param childRoot 
	 * @return 
	 */
	Node* SearchRecursively(const T& key, Node* childRoot) const;
};

template <typename T, typename NodeType>
BST<T, NodeType>::BST(): BinaryTreeBase<T, NodeType>()
{
}

template <typename T, typename NodeType>
BST<T, NodeType>::~BST()
{
}

template <typename T, typename NodeType>
typename BST<T, NodeType>::Node* BST<T, NodeType>::Search(const T& key) const
{
	return SearchRecursively(key, BinaryTreeBase<T>::root);
}

template <typename T, typename NodeType>
typename BST<T, NodeType>::Node* BST<T, NodeType>::SearchRecursively(const T& key, Node* childRoot) const
{
	if(childRoot)
	{
		// 如果 childRoot 不为空
		
		if(key < childRoot->data)
		{
			// 如果 key 小于当前节点元素，搜索左子树
			return SearchRecursively(key, childRoot->left);
		}
		else if(key > childRoot->data)
		{
			// 如果 key 大于当前节点元素，搜索右子树
			return SearchRecursively(key, childRoot->right);
		}
		else
		{
			// 如果 key 等于当前元素，说明搜索成功，返回当前节点
			return childRoot;
		}
	}
	else
	{
		// 如果 childRoot 为空
		return nullptr;
	}
}

template <typename T, typename NodeType>
typename BST<T, NodeType>::Node* BST<T, NodeType>::FindMax(Node* rootNode) const
{
	if(rootNode)
	{
		// 二叉搜索树，最大值一直沿着右子树搜索
		Node* finder = rootNode;
		while(finder->right)
			finder = finder->right;

		return finder;
	}
	else
	{
		return nullptr;
	}
}